/**
 * 在一个 n * m 的二维数组中，每一行都按照从左到右 非递减 的顺序排序，
 * 每一列都按照从上到下 非递减 的顺序排序。请完成一个高效的函数，
 * 输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 * @param {*} nums 
 * @param {*} target 
 */
function searchMatrix(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        if (search(nums[i], target)) return true;
    }
    return false;
}

/**
 * 二分查找法
 * @param {*} arr 
 * @param {*} target 
 * @returns 
 */
function search(arr, target) {
    let left = 0, right = arr.length - 1;
    while (left <= right) {
        let mid = parseInt((right - left) / 2) + left;
        if (arr[mid] === target) return true;
        else if (arr[mid] < target) right = mid - 1;
        else left = mid + 1;
    }
    return false;
}